

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" href="/img/favicon.png">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="author" content="Cheney">
  <meta name="keywords" content="Coding">
  
    <meta name="description" content="判断链表是否有环路，并求出环路出现的位置。判断两个链表是否相交等功能的实现。">
<meta property="og:type" content="article">
<meta property="og:title" content="带环、相交链表问题">
<meta property="og:url" content="https://cheney822.gitee.io/2020/12/04/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E5%B8%A6%E7%8E%AF%E3%80%81%E7%9B%B8%E4%BA%A4%E9%93%BE%E8%A1%A8%E9%97%AE%E9%A2%98/index.html">
<meta property="og:site_name" content="Cheney blog">
<meta property="og:description" content="判断链表是否有环路，并求出环路出现的位置。判断两个链表是否相交等功能的实现。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/6276728149da4368bb22ce23f7f7888f-20220405210623053-20220405210633007.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/5e81d04d8f524a9bb4d7063593789c5e-20220405210623214-20220405210633068.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/76131aa86a744bfe99202d89bf559c3a-20220405210623399-20220405210633131.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/48c53e0b0f844cc9b93639563ff6c99b-20220405210623587-20220405210633170.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/58cd83d0a33d47578c15ba0d8e3a080b-20220405210623708-20220405210633206.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/3029834735884386b1e0ca4c59b53ed9-20220405210623867-20220405210633245.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/bf653d8f0560430cbb1dc68d7981627d-20220405210624025-20220405210633288.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/f903d46313284841b13854c4cb57d564-20220405210624142-20220405210633325.png">
<meta property="og:image" content="https://imgbed.cheney.cc/picgo/89b6d232b4c74253857f15e3b6a78893-20220405210624341-20220405210633373.png">
<meta property="article:published_time" content="2020-12-04T05:14:00.000Z">
<meta property="article:modified_time" content="2022-04-05T13:14:28.419Z">
<meta property="article:author" content="Cheney">
<meta property="article:tag" content="C++">
<meta property="article:tag" content="链表">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://imgbed.cheney.cc/picgo/6276728149da4368bb22ce23f7f7888f-20220405210623053-20220405210633007.png">
  
  
  <title>带环、相交链表问题 - Cheney blog</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4/github-markdown.min.css" />
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hint.css@2/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.css" />
  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"cheney822.gitee.io","root":"/","version":"1.8.14","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":1},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.4.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand" href="/">
      <strong>Cheney Blog</strong>
    </a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
              &nbsp;<i class="iconfont icon-search"></i>&nbsp;
            </a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('https://imgbed.cheney.cc/Blog_config/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="带环、相交链表问题">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-12-04 13:14" pubdate>
        2020年12月4日 下午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      6.8k 字
    </span>
  

  
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      34 分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">带环、相交链表问题</h1>
            
            <div class="markdown-body">
              <h1 id="一、问题描述："><a href="#一、问题描述：" class="headerlink" title="一、问题描述："></a>一、问题描述：</h1><p>基于课程上机关于单链表的作业，要求进一步实现以下需求:</p>
<ul>
<li><p>1.构造链表后，将元素值为 m 和 n（从键盘输入，如有多个相同元素值，仅考虑首个出现的元素）的节点建立连接，注意判断节点出现的先后关系，将后面出现的节点（假设为 n）的链域连到先出现的节点（假设为 m），将原 n 节点的后续节点搬迁到原单链表的头部，形成以下双头相交链表（如果使用带头结点的链表，搬迁过程中请自行额外增加一个头节点）；<br><img src="https://imgbed.cheney.cc/picgo/6276728149da4368bb22ce23f7f7888f-20220405210623053-20220405210633007.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
</li>
<li><p>2.利用课程 ppt 中关于判断链表是否有环的方法，判断链表是否有环路，并求出环路出现的<br>位置，即 m，n 节点的指针，请使用环路判断函数（输入为链表头指针），不可直接查找 m,n，<br>支持使用 2 个不同的链表头部指针进行查询；</p>
</li>
<li><p>3.将环路链接取消，恢复成单链表，并根据表头指针（输入）求解链表的中间节点（输出中<br>间节点的值并返回指针），注意：不要将链表转换成数组来求解；</p>
</li>
<li><p>4.编写函数，判断两个链表是否相交，函数输入为双头相交链表的两个头指针并输出相交的<br>指针，如没有相交则返回 NULL。<br>注意：判断相交是基于指针的比较（判断是否有相同的节点指针出现在两个链表中）而不是节点的值的比较。</p>
</li>
</ul>
<h1 id="二、需求分析："><a href="#二、需求分析：" class="headerlink" title="二、需求分析："></a>二、需求分析：</h1><p>首先要设计生成一个直链，然后考虑如何将其连接成符合题意的双头相交链表，设计判断环路的方法能够判断所给的链表是否有环并且返回环的入口，封装成函数供其他函数调用，最后就是判断链表相交，不应局限于题目所给条件而要充分考虑两链表相交的各种情况。</p>
<h1 id="三、概要设计："><a href="#三、概要设计：" class="headerlink" title="三、概要设计："></a>三、概要设计：</h1><p>首先构建一个单链表，然后根据用户输入的m，n值依照题目要求的方式，构造符合要求的双头相交链表，并能够还原成原来的单链表。设计函数判断一个链表是否有环。编写函数判断给定的两个链表是否相交。</p>
<h2 id="1、数据结构定义："><a href="#1、数据结构定义：" class="headerlink" title="1、数据结构定义："></a>1、数据结构定义：</h2><p>程序涉及到一个链表的储存，且涉及到的操作不多，故采用结构体的方式定义：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><div class="code-wrapper"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></div></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> <span class="hljs-title class_">LinkList</span><br>&#123;   <span class="hljs-type">int</span> Data=<span class="hljs-number">-999</span>;<br>    LinkList* next=<span class="hljs-literal">NULL</span>;<br>&#125;LinkList;<span class="hljs-comment">//定义“链表”结构体，用于表示链表及相关节点</span><br>LinkList* CCListHead = <span class="hljs-keyword">new</span> LinkList;<span class="hljs-comment">//开始构建的单链表的头节点</span><br>LinkList* CCListHead2 = <span class="hljs-literal">NULL</span>;<span class="hljs-comment">//对单链表处理过后的第二个头节点</span><br></code></pre></td></tr></table></figure>

<h2 id="2、模块设计："><a href="#2、模块设计：" class="headerlink" title="2、模块设计："></a>2、模块设计：</h2><p>1）main：显示菜单，并根据用户的选择做出判断，在其中调用其他函数完成功能<br>2）MakeLinklist()：以上述已定义的头节点为头构建一个长为100的数值为随机数的单链表。<br>3）连接成环function1():将上述已经建立好的单链表依据要求连接成双头相交链表。<br>4）判断环路function2():利用快慢指针法，以判断上述节点为头的链表是否有环，并返回环的入口<br>5）取消环，并输出中间节点function3():用连接环时的相反的操作把环路取消，并根据输入的头节点输出对应的中间节点。<br>6）判断相交function4():判断已有的两个头节点所指示的链表是否相交。</p>
<h2 id="3、各模块间的调用关系："><a href="#3、各模块间的调用关系：" class="headerlink" title="3、各模块间的调用关系："></a>3、各模块间的调用关系：</h2><p><img src="https://imgbed.cheney.cc/picgo/5e81d04d8f524a9bb4d7063593789c5e-20220405210623214-20220405210633068.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<h1 id="四、详细设计"><a href="#四、详细设计" class="headerlink" title="四、详细设计"></a>四、详细设计</h1><p>主要算法设计：</p>
<h2 id="1）直链的构建："><a href="#1）直链的构建：" class="headerlink" title="1）直链的构建："></a>1）直链的构建：</h2><p>先构建一个没有重复数字的随机数数组   </p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i &lt;<span class="hljs-number">150</span> ; i++) &#123;<br>        <span class="hljs-type">int</span> Same = <span class="hljs-number">1</span>;<br>        A[i] = <span class="hljs-built_in">rand</span>() / (<span class="hljs-type">double</span>)RAND_MAX * (<span class="hljs-number">200</span>);<br>        <span class="hljs-keyword">while</span> (Same) &#123;<span class="hljs-comment">//直到没有重复数字才结束循环</span><br>            Same = <span class="hljs-number">0</span>;<br>            <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> j = <span class="hljs-number">0</span>; j &lt; i; j++) &#123;<br>                <span class="hljs-keyword">if</span> (A[i] == A[j]) &#123;<br>                    Same = <span class="hljs-number">1</span>;<span class="hljs-comment">//表示有重复数字，需要重新生成随机数</span><br>                    A[i] = <span class="hljs-built_in">rand</span>() / (<span class="hljs-type">double</span>)RAND_MAX * (<span class="hljs-number">200</span>);<br>                    <span class="hljs-keyword">break</span>;<br>                &#125;<br>            &#125;<br>        &#125;       <br>&#125;<br></code></pre></td></tr></table></figure>

<p>然后利用此数组中的各元素的值来构建链表</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">while</span>(<span class="hljs-number">1</span>)<br>    &#123;<br>        Current-&gt;Data = A[i++];<br>        <span class="hljs-comment">//Current-&gt;Data = i++;</span><br>        <span class="hljs-keyword">if</span> (i == <span class="hljs-number">100</span>)<span class="hljs-keyword">break</span>;<br>        Current-&gt;next = <span class="hljs-keyword">new</span> LinkList;<br>        Current = Current-&gt;next;<br>    &#125;<br></code></pre></td></tr></table></figure>

<h2 id="2）判断环路：利用快慢指针法判断环路"><a href="#2）判断环路：利用快慢指针法判断环路" class="headerlink" title="2）判断环路：利用快慢指针法判断环路"></a>2）判断环路：利用快慢指针法判断环路</h2><p>原理：设置一个快指针fast每次走两步即Fast = Fast-&gt;next-&gt;next;//快指针走两步，设置一个慢指针slow每次走一步即 Slow = Slow-&gt;next;//慢指针走一步；初始状态 两个指针都从头开始走，如果有环的话则由于两指针有速度差，则必定会在环中某点相遇，反之在Fast走到尾部之前，两指针都不会相遇，以此来判断给定的头指针所指示的链表是否有环。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-function">LinkList* <span class="hljs-title">function2</span><span class="hljs-params">(LinkList* Head)</span> </span>&#123;<br>    LinkList* Slow = Head;<br>    LinkList* Fast = Head;<br>    <span class="hljs-type">int</span> isLoop = <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">while</span> (Slow-&gt;next != <span class="hljs-literal">NULL</span> &amp;&amp; Fast-&gt;next-&gt;next != <span class="hljs-literal">NULL</span>) <br>    &#123;<br>        Slow = Slow-&gt;next;<span class="hljs-comment">//慢指针走一步</span><br>        Fast = Fast-&gt;next-&gt;next;<span class="hljs-comment">//快指针走两步</span><br>        <span class="hljs-keyword">if</span> (Slow == Fast) &#123;<span class="hljs-comment">//快慢相遇</span><br>            isLoop = <span class="hljs-number">1</span>;<span class="hljs-comment">///则有环</span><br>            <span class="hljs-keyword">break</span>;<br>        &#125;<br>        <span class="hljs-keyword">if</span>(Fast-&gt;next==<span class="hljs-literal">NULL</span>)<span class="hljs-comment">//快指针到尾 则结束</span><br>            <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;<br>    &#125;<br>    <span class="hljs-keyword">if</span> (isLoop) &#123;<span class="hljs-comment">//有环的话 就判断环的入口</span><br>        Slow = Head;<br>        <span class="hljs-keyword">while</span> (Slow != Fast) &#123;<br>            Slow = Slow-&gt;next;<br>            Fast = Fast-&gt;next;<br>        &#125;<br>        <span class="hljs-keyword">return</span> Slow;<br>    &#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;<br>&#125;<br></code></pre></td></tr></table></figure>

<p>如果有环路，判断环入口的方法：第一次相遇点到入口的距离=头指针到连接点入口的距离，因此，分别从第一次相遇点、头指针head开始走，再次相遇的那个点就是连接点。</p>
<h2 id="3）连接成环：将单链表按要求转化为双交头链表。"><a href="#3）连接成环：将单链表按要求转化为双交头链表。" class="headerlink" title="3）连接成环：将单链表按要求转化为双交头链表。"></a>3）连接成环：将单链表按要求转化为双交头链表。</h2><p>首先判断是否已经是双头相交链表，若是则返回错误提示信息，若不是则可以在给出的链表的100个数值里面挑选两个作为m n，自动判断先出现的为m，并按照题目所给的方法连接m、n得到要求的双头相交链表，并将新得到的链表头记为Head2.</p>
<p>步骤：</p>
<ul>
<li>先找到用户输入的m，n值对应的链表节点，小编号节点的指针记为MM大编号记为NN。</li>
<li>然后对链表进行再次连接：NN后面的节点用Head2 指示，链表尾部节点由空改为指向MM，NN后继指向MM。即完成了对链表的再次连接</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><code class="hljs cpp">CCListHead2 = NN-&gt;next;<br>   Tail-&gt;next = MM;<br>   NN-&gt;next = MM;<br></code></pre></td></tr></table></figure>

<h2 id="4）取消环并输出中间节点"><a href="#4）取消环并输出中间节点" class="headerlink" title="4）取消环并输出中间节点:"></a>4）取消环并输出中间节点:</h2><p>先判断头指针是否为空，有一个为空则无法恢复。<br>要恢复成单链表只需要找到四个位置：m的位置，n的位置，原链表尾的位置，原n后继的位置。<br>方法：m的位置只需要调用2即可返回入口即m的位置，n用Current指针遍历链表，并设置PreCurrent保存Current的前驱节点，当Current第二次经过m时的PreCurrent即为n的位置（因为第一次不在环中），原链表尾类似的方法遍历Head2（连接链表后制造出的头节点）第一次到m时对应的PreCurrent即为原链表尾记为tail，易判断Head2即为原n的后继。<br>判断完上述位置后，只需将n的后继改为Head2 指示的节点并让tail指向空即可。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-keyword">if</span> (CCListHead == <span class="hljs-literal">NULL</span> || CCListHead2 == <span class="hljs-literal">NULL</span>) &#123;<br>        cout &lt;&lt; <span class="hljs-string">&quot;*****当前无法恢复成单链*****&quot;</span>&lt;&lt;endl;<br>        <span class="hljs-keyword">return</span> ;<br>    &#125;<br><br>    LinkList* Tail = <span class="hljs-literal">NULL</span>;<br>    LinkList* NN = <span class="hljs-literal">NULL</span>;<br><br>    LinkList* MM = <span class="hljs-built_in">function2</span>(CCListHead);<br>    LinkList* Current = CCListHead2;<br>    LinkList* PreCurrent = <span class="hljs-keyword">new</span>  LinkList;<br>    PreCurrent-&gt;next = Current;<br><br>    <span class="hljs-keyword">for</span> (Current = CCListHead2; Current != MM; ) &#123;<br>          PreCurrent = PreCurrent-&gt;next;<br>        Current = Current-&gt;next;<br>    &#125;<br>    Tail = PreCurrent;<br><br>    Current = CCListHead;<br>    PreCurrent = <span class="hljs-keyword">new</span>  LinkList;<br>    PreCurrent-&gt;next = CCListHead;<br><br>    <span class="hljs-type">int</span> time = <span class="hljs-number">0</span>;<span class="hljs-comment">//第几次到达MM</span><br>    <span class="hljs-keyword">while</span>(time != <span class="hljs-number">4</span>)<br>    &#123;<br>        PreCurrent = PreCurrent-&gt;next;<br>        Current = Current-&gt;next;<br>        <span class="hljs-keyword">if</span>(Current == MM) time++;<br>    &#125;<br>    NN = PreCurrent;<br>    NN-&gt;next = CCListHead2;<br>      <br>  <br>    CCListHead2 = <span class="hljs-literal">NULL</span>;<br>      Tail-&gt;next = <span class="hljs-literal">NULL</span>;<br></code></pre></td></tr></table></figure>

<p>根据表头指针（输入）求解链表的中间节点：<br>读入用户输入的起点和终点后，遍历链表，遇到数据等于其中之一就开始输出节点的值，直到遇到用户输入的另外一个为止。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><code class="hljs cpp"><span class="hljs-type">int</span> m, n;<br>   cout &lt;&lt; <span class="hljs-string">&quot;\n*****请输入要输出中间节点的范围 m，n*****&quot;</span> &lt;&lt; endl;<br>   cin &gt;&gt; m &gt;&gt; n;<br><br>   <span class="hljs-type">int</span> i = <span class="hljs-number">0</span>, MLoc = <span class="hljs-number">-1</span>, NLoc = <span class="hljs-number">-1</span>;<br>   <span class="hljs-keyword">for</span> (Current = CCListHead; Current != <span class="hljs-literal">NULL</span>; Current = Current-&gt;next)<br>   &#123;<br>       <span class="hljs-keyword">if</span> (Current-&gt;Data == m) <br>           MLoc = i;<br>       <span class="hljs-keyword">if</span> (Current-&gt;Data == n) <br>           NLoc = i;<br>       <br>       i++;<br>   &#125;<br>   <span class="hljs-keyword">if</span> (MLoc == <span class="hljs-number">-1</span> || NLoc == <span class="hljs-number">-1</span>) &#123;<br>       cout &lt;&lt; <span class="hljs-string">&quot;*****没有对应的两个节点******&quot;</span>;<br>       <span class="hljs-keyword">return</span>;<br>   &#125;<br><br>   <span class="hljs-type">int</span> start = <span class="hljs-number">0</span>;<br>   <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>, Current = CCListHead; Current != <span class="hljs-literal">NULL</span>; Current = Current-&gt;next,i++) &#123;<br>       <span class="hljs-keyword">if</span> (i == <span class="hljs-built_in">min</span>(MLoc, NLoc))start = <span class="hljs-number">1</span>;<br>       <span class="hljs-keyword">if</span> (start) cout &lt;&lt; Current-&gt;Data &lt;&lt; <span class="hljs-string">&quot;--&quot;</span>;<br>       <span class="hljs-keyword">if</span> (i == <span class="hljs-built_in">max</span>(MLoc, NLoc))start = <span class="hljs-number">0</span>;<br>   &#125;<br></code></pre></td></tr></table></figure>

<h2 id="5）判断相交-此问题分三种情况讨论，即：两直链、两环、环-直链。"><a href="#5）判断相交-此问题分三种情况讨论，即：两直链、两环、环-直链。" class="headerlink" title="5）判断相交:此问题分三种情况讨论，即：两直链、两环、环+直链。"></a>5）判断相交:此问题分三种情况讨论，即：两直链、两环、环+直链。</h2><p>情况如图所示： <img src="https://imgbed.cheney.cc/picgo/76131aa86a744bfe99202d89bf559c3a-20220405210623399-20220405210633131.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>首先，判断链表是否有环的方法已经在2给出，直接调用即可。</p>
<ul>
<li>两直链：判断两直链是否相交只需判断两直链尾指针是否一样即可，一样则说明两直链在尾部之前有相交。</li>
<li>两环：两环相交在公共环的部分可能有一个或者两个入口，不管有几个，首先利用2给出的方法判断A链表环的入口，然后在B中遍历，判断A的入口是否在其中（注意带环链表的遍历，结束条件应该为第二次经过环入口），在的话则相交，进一步可以判断有一个还是两个入口。</li>
<li>环+直链：此情况直接可判断为无相交。</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><code class="hljs cpp">LinkList* Ahead=CCListHead;<br>   LinkList* Bhead=CCListHead2;<br>   LinkList* xx = <span class="hljs-built_in">function2</span>(Ahead);<br>   LinkList* yy = <span class="hljs-built_in">function2</span>(Bhead);<br><br>   LinkList* Current，PreCurrent;<br>   LinkList* AA，BB;<br><br>   <span class="hljs-keyword">if</span> (xx==<span class="hljs-literal">NULL</span>&amp;&amp;yy==<span class="hljs-literal">NULL</span>) &#123;<br>       <span class="hljs-comment">//两个直链</span><br>       PreCurrent = <span class="hljs-keyword">new</span>  LinkList;<br>       PreCurrent-&gt;next = Ahead;<br>       <span class="hljs-keyword">for</span> (Current = Ahead; Current != <span class="hljs-literal">NULL</span>; ) &#123;<br>           PreCurrent = PreCurrent-&gt;next;<br>           Current = Current-&gt;next;<br>       &#125;<br>       AA = PreCurrent;<br>       PreCurrent = <span class="hljs-keyword">new</span>  LinkList;<br>       PreCurrent-&gt;next = Bhead;<br>       <span class="hljs-keyword">for</span> (Current = Bhead; Current != <span class="hljs-literal">NULL</span>; ) &#123;<br>           PreCurrent = PreCurrent-&gt;next;<br>           Current = Current-&gt;next;<br>       &#125;<br>       BB = PreCurrent;<br><br>       <span class="hljs-keyword">if</span>(AA==BB)&#123;<br>           cout &lt;&lt; <span class="hljs-string">&quot;*****直链+直链，相交！！！*****&quot;</span>;<br>       &#125;<br>       <span class="hljs-keyword">else</span> &#123;<br>           cout &lt;&lt; <span class="hljs-string">&quot;*****直链+直链，不相交！！！*****&quot;</span>;<br>           <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;<br>       &#125;<br>   &#125;<br>   <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (xx != <span class="hljs-literal">NULL</span> &amp;&amp; yy != <span class="hljs-literal">NULL</span>) &#123;<br>       <span class="hljs-comment">//两个环</span><br>       LinkList* EntranceA;<br>       EntranceA= <span class="hljs-built_in">function2</span>(Ahead);<br>       LinkList* EntranceB;<br>       EntranceB = <span class="hljs-built_in">function2</span>(Ahead);<br><br>       <span class="hljs-type">int</span> time = <span class="hljs-number">0</span>;<span class="hljs-comment">//第几次到达MM</span><br>       <span class="hljs-type">int</span> Jiao = <span class="hljs-number">0</span>;<br>       Current = Ahead;<br>       <span class="hljs-keyword">while</span> (time != <span class="hljs-number">4</span>)<br>       &#123;<br>           Current = Current-&gt;next;<br>           <span class="hljs-keyword">if</span> (Current == EntranceA) time++;<br>           <span class="hljs-keyword">if</span> (Current == EntranceB) &#123;<br>               cout &lt;&lt; <span class="hljs-string">&quot;*****环+环，相交！！！*****&quot;</span>;<br>               Jiao = <span class="hljs-number">1</span>;<br>               <span class="hljs-keyword">break</span>;<br>           &#125;<br>       &#125;<br>       <span class="hljs-keyword">if</span>(!Jiao)cout &lt;&lt; <span class="hljs-string">&quot;*****环+环，不相交！！！*****&quot;</span>;<br>       <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;<br><br>   &#125;<br>   <span class="hljs-keyword">else</span> &#123;<br>       cout &lt;&lt; <span class="hljs-string">&quot;*****直链+环，不相交！！！*****&quot;</span>;<br>       <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;<br>   &#125;<br></code></pre></td></tr></table></figure>

<p>以上就是本程序的核心代码部分</p>
<h1 id="五、用户手册："><a href="#五、用户手册：" class="headerlink" title="五、用户手册："></a>五、用户手册：</h1><p>打开程序后，程序出现菜单，选择你需要的功能，输入对应的序号按下回车即可，当选择功能一即连接成环时，程序会展示出预先生成的链表中的所有一百个值，选择两个值输入，系统自动判断先出现的为M反之为N，并连接成题目要求的链表，随后展示出连接的情况。当选择功能三时，如果已经存在相交链表则将其恢复成初始状态，随后展示出预先生成的链表中的所有一百个值，选择两个值输入后，程序会输出由用户输入的两个值对应节点的中间所有节点的值。其他功能类似，可反复使用。</p>
<h1 id="六、调试报告："><a href="#六、调试报告：" class="headerlink" title="六、调试报告："></a>六、调试报告：</h1><p>测试过程中出现了以下几个问题：<br>恢复成直链失败：<br>尝试使用恢复成直链后，再次输出的链表与原链表不同，表明未正确恢复，于是将链表中的数据全部换成连续的一到一百，然后再次尝试就很容易发现出错的位置，分析后发现是N的位置找的不对，考虑到采用遍历的方法判断当前指针到达M则其后继即为N，但这是在环中的情况，在此之前还要经历在前半段直链的情况，所以用这种方法每次找到的都是在直链部分M的前驱而不是N。修改方法：用一个统计遍历次数的变量time初始化为零，每次当前指针遍历到M 时time就加一，这样只要time不是零，在当前指针遍历到M的时候其前驱就是N，修改过后程序即可输出预期的结果。<br>又尝试了以下改进：<br>对链表的相交情况进行可视化，即输出连接后的双头相交链表，具体采取的方法：<br>依次输出Head1到M，M到N，Head2到M即可表示出相交后的链表的具体情况，分析后发现与预期完全吻合。</p>
<h1 id="八、测试结果："><a href="#八、测试结果：" class="headerlink" title="八、测试结果："></a>八、测试结果：</h1><p>测试结果如下：<br> <img src="https://imgbed.cheney.cc/picgo/48c53e0b0f844cc9b93639563ff6c99b-20220405210623587-20220405210633170.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 1连接成环</p>
<p><img src="https://imgbed.cheney.cc/picgo/58cd83d0a33d47578c15ba0d8e3a080b-20220405210623708-20220405210633206.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 2判断环路</p>
<p><img src="https://imgbed.cheney.cc/picgo/3029834735884386b1e0ca4c59b53ed9-20220405210623867-20220405210633245.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 3判断相交<br> <img src="https://imgbed.cheney.cc/picgo/bf653d8f0560430cbb1dc68d7981627d-20220405210624025-20220405210633288.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 4转化成直链并输出中间节点</p>
<p><img src="https://imgbed.cheney.cc/picgo/f903d46313284841b13854c4cb57d564-20220405210624142-20220405210633325.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 5未连接状态下判断环<br> <img src="https://imgbed.cheney.cc/picgo/89b6d232b4c74253857f15e3b6a78893-20220405210624341-20220405210633373.png" srcset="/img/loading.gif" lazyload alt="在这里插入图片描述"></p>
<p>图 6 改进后的界面（输出链表的相交情况）</p>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/C/">C++</a>
                    
                      <a class="hover-with-bg" href="/tags/%E9%93%BE%E8%A1%A8/">链表</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/12/05/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%BA%94%E7%94%A8%E5%8F%8A%E5%AF%B9%E6%AF%94/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">排序算法应用及对比</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/12/03/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AE%9E%E9%AA%8C--%E5%A4%A7%E6%95%B0%E8%BF%90%E7%AE%97%E4%B9%8B%E8%AE%A1%E7%AE%97n%E7%9A%84%E9%98%B6%E4%B9%98%20(n%E2%89%A520)/">
                        <span class="hidden-mobile">大数运算之计算n的阶乘 (n≥20)</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    

    
      <a id="scroll-top-button" aria-label="TOP" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://cheney822.gitee.io/" target="_blank" rel="nofollow noopener"><span>备用网址</span></a> 
  </div>
  

  
  <!-- 备案信息 -->
  <div class="beian">
    <span>
      <a href="http://beian.miit.gov.cn/" target="_blank" rel="nofollow noopener">
        皖ICP备2022002876号-1
      </a>
    </span>
    
  </div>


  
</footer>


  <!-- SCRIPTS -->
  
  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4/dist/js/bootstrap.min.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  <script  src="/js/local-search.js" ></script>



  
    <script  src="/js/img-lazyload.js" ></script>
  



  



  
    <script  src="https://cdn.jsdelivr.net/npm/tocbot@4/dist/tocbot.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3/dist/jquery.fancybox.min.js" ></script>
  
  
    <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4/anchor.min.js" ></script>
  
  
    <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js" ></script>
  






  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
        typing(title);
      
    })(window, document);
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>


</body>
</html>
